package main

import (
	"fmt"
)

func main() {

	//声明数组
	numbers := []int{35, 33, 42, 10, 14, 19, 27, 44, 26, 31}
	//numbers := utils.GetRandSlices(10)
	fmt.Printf("%v \n", numbers)
	//开始排序： 第一遍 左、右
	QuickSort(0, len(numbers)-1, &numbers)
	fmt.Printf("%v \n", numbers)
}

func QuickSort(left, right int, numbers *[]int) {
	if right-left <= 0 { //数据已经不能再被分割。
		return
	} else {
		pivot := (*numbers)[right] //找到基准元素

		partIndex := Partition(left, right, pivot, numbers) //执行定位迁移操作。获取到基准原始交叉点。

		//-----------------------------------------------------
		//此时的数据已经由交叉点分割成左右两份。分别对左右的元素执行如此操作。
		QuickSort(left, partIndex-1, numbers)  //小于基准（左边）的元素，执行快速排序
		QuickSort(partIndex+1, right, numbers) //大于基准（右边）的元素，执行快速排序
	}
}

func Partition(left, right, pivot int, numbers *[]int) int {
	lo := left
	hi := right - 1 //不包含基准元素位置
	for {

		// 移动 `lo` 位置找到大于，`pivot` 的元素。
		for (*numbers)[lo] < pivot {
			lo++
		}

		// 移动 `hi` 位置找到小于，`pivot` 的元素。
		for hi > 0 && (*numbers)[hi] > pivot {
			hi--
		}

		//当移动的点交叉，本次迁移完成。退出
		if lo >= hi {
			break
		} else {
			//交换两个元素位置。
			fmt.Printf(" 交换 :%d,%d\n", (*numbers)[lo], (*numbers)[hi])
			(*numbers)[lo], (*numbers)[hi] = (*numbers)[hi], (*numbers)[lo]
		}
	}
	//当 `hi` 和 `lo` 交叉以后，数据已经通过 `pivot` 分割成左右两段。那么 `pivot` 就需要移动到交叉点的位置。
	if lo != right {
		fmt.Printf(" 交换 :%d,%d\n", (*numbers)[lo], (*numbers)[right])
		(*numbers)[lo], (*numbers)[right] = (*numbers)[right], (*numbers)[lo]
	}
	//返回交叉点。
	return lo
}
